/*
 * permutations.h
 *
 *  Created on: May 2, 2011
 *      Author: shai
 */

#ifndef PERMUTATIONS_H_
#define PERMUTATIONS_H_

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <numeric>
#include <utility>
#include <vector>
#include <cassert>

#include "../contrib/combination.hpp"

extern "C"
{

//TODO: template
class permutation
/*
 * Represents a permutation composed of disjoint c-cycles.
 * The permuted elements are stored in the indices vector, elements n*cycleSize to n*(cycleSize+1) - 1
 * represent the nth cycle, where every element is to the (cyclic left of it's mapped value).
 * The current implementation holds a set of indices which could be remapped, profiling will
 * determine if that design prevails.
 */
{
public:
	int cycleSize;
	int cycles; //counts how many cycles are present
	std::vector<int> indices;

	permutation(int n,int c) : cycleSize(c), cycles(0), indices(n)
	{
		for (int i=0; i<n ; i++) indices[i] = i; //The ID permutation
	}

	//copy ctor
	permutation(const permutation& p) : cycleSize(p.cycleSize), cycles(p.cycles), indices(p.indices)
	{
	}

	//TODO: does the search have to be linear?
	int permute(int index)
	{
		for (int i=0 ; i<cycles ; i++)
		{
			for (int j=0 ; j<cycleSize-1 ; j++)
				if (indices[i*cycleSize+j] == index) return indices[i+j+1];
			if (indices[cycleSize*(i+1)-1] == index) return indices[cycleSize];
		}
		return index;
	}

	permutation compose(int pow)
	{
		pow %= cycleSize;
		permutation power(*this);
		for (int i=1 ; i<cycles*cycleSize ; i++)
		{
			for(int j=0; j<pow; j++)
				power.indices[i] = permute(power.indices[i-1]);

		}
		return power; //TODO i added this (Or) what this function does??
	}
};

double printPermutation(const permutation* p);

/*
 * Given a group size n and cycle size c, creates all permutations which are compositions of c-cycles and
 * operates on them.
 *
 * n - size of group
 * c - cycle size
 * action - action to perform on generated permutations (optional)
 *
 * returns: the sum of return values of the actions, or sum of permutations in case no action was passed
 */
//TODO: replace n with a templated container
int find_all_cycles(int n, int c, std::function<int (permutation*)> action = NULL);
}
#endif /* PERMUTATIONS_H_ */

